package 划分字母区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/25 20:20
 * @description:
 */
public class WrongSolution {
    public List<Integer> partitionLabels(String s) {
        // greedy
        // 维护一个长度 26 的int数组，记录字母当前被划分到哪一个区间（比如a被划分到串s的第五个位置之前的区间，就记录5）
        // 当串 s 前后字符不相等时，我们就进行一次划分。划分后的前一个字符如果再 int 数组中存在非0值，那么我们就进行区间合并
        // 合并的区间是 int 中的值 到 当前串 s 的位置，并修改 int 中的值
        // 局部最优：只要前后字符不相等我们就划分，如果不能划分就进行合并。始终保持当前的划分是最大且合法的

        int[] interval = new int[26];
        Arrays.fill(interval, 0);
        int[] result = new int[26]; // 最多划分 26 段
        int index = 0;
        result[index++] = 1;
        interval[s.charAt(0) - 97] = 1;
        for (int i = 1; i < s.length(); i++) {
            char curChar = s.charAt(i);
            char preChar = s.charAt(i - 1);
            if (curChar != preChar) {
                int intervalVal = interval[curChar - 97];
                if (intervalVal != 0) {
                    // 字符串段需要进行合并
                    while (true) {
                        index--;
                        if (result[index] == intervalVal) {
                            // 合并 intervalVal 到 i之间的串
                            interval[curChar - 97] = i;
                            result[index++] = i;
                            break;
                        }
                        result[index] = 0;
                    }
                } else {
                    // 跟新字母对应的区间位置
                    interval[curChar - 97] = i;
                    // 新增一个字符串段
                    result[index++] = i;
                }
            }
        }
        List<Integer> list = new ArrayList<>();
        if (result[0] != 0) {
            list.add(result[0]);
        }
        for (int i = 1; i < index; i++) {
            list.add(result[i] - result[i - 1]);
        }
        return list;
    }
}
